package com.test.daily.leetcode.y2022.m07.day0724.v03;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @author Tom on 2022/7/24
 */
public class Solution {
    public int islandNum1(int[][] board) {
        int islandNum = 0;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 1) {
                    islandNum++;
                    infect(board, i, j);
                }
            }
        }
        return islandNum;
    }

    public int islandNum2(int[][] board) {
        List<Dot> list = new ArrayList<>();
        int m = board.length;
        int n = board[0].length;
        Dot[][] dots = new Dot[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] == 1){
                    dots[i][j] = new Dot();
                    list.add(dots[i][j]);
                }
            }
        }
        UnionFind1 uf = new UnionFind1(list);
        for(int i = 1; i < n; i++){
            if(board[0][i] == 1 && board[0][i-1] == 1){
                uf.union(dots[0][i], dots[0][i-1]);
            }
        }
        for(int j = 1; j < m; j++){
            if(board[j][0] == 1 && board[j-1][0] == 1){
                uf.union(dots[j][0], dots[j-1][0]);
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(board[i][j] == 1){
                    if(board[i-1][j] == 1){
                        uf.union(dots[i][j], dots[i-1][j]);
                    }
                    if(board[i][j-1] == 1){
                        uf.union(dots[i][j], dots[i][j-1]);
                    }
                }
            }
        }
        return uf.size();
    }

    public void infect(int[][] board, int i, int j) {
        if (i < 0 || i == board.length || j < 0 || j == board[0].length || board[i][j] == 0) {
            return;
        }
        board[i][j] = 0;
        infect(board, i - 1, j - 1);
        infect(board, i - 1, j);
        infect(board, i + 1, j);
        infect(board, i + 1, j - 1);
    }

    public static class Dot {
    }

    public static class Node<V> {
        V value;

        public Node(V value) {
            this.value = value;
        }
    }

    public static class UnionFind1<V> {
        public HashMap<Node<V>, Node<V>> parent;
        public HashMap<V, Node<V>> nodes;
        public HashMap<Node<V>, Integer> sizeMap;
        public int size;

        public UnionFind1(List<V> list) {
            int n = list.size();
            size = n;
            parent = new HashMap<>();
            nodes = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V dot : list) {
                Node node = new Node(dot);
                parent.put(node, node);
                nodes.put(dot, node);
                sizeMap.put(node, 1);
            }
        }
        public Node<V> findFather(V v){
            Node<V> node = nodes.get(v);
            Stack<Node> path = new Stack<>();
            while(node != parent.get(node)){
                path.push(node);
                node = parent.get(node);
            }
            while(path.size() != 0){
                parent.put(path.pop(), node);
            }
            return node;
        }
        public boolean isSameFather(V a, V b){
            return findFather(a) == findFather(b);
        }
        public void union(V a, V b){
            Node fatherA = findFather(a);
            Node fatherB = findFather(b);
            if(fatherA != fatherB){
                int sizeA = sizeMap.get(fatherA);
                int sizeB = sizeMap.get(fatherB);
                Node big = sizeA > sizeB ? fatherA : fatherB;
                Node small = big == fatherA ? fatherB: fatherA;
                parent.put(small, big);
                sizeMap.put(fatherB, sizeA + sizeB);
                sizeMap.remove(small);
                size--;
            }
        }
        public int size(){
            return size;
        }
    }
}
